Number of valid subarrays [Mono Stack]

Time: O(N); Space: O(N); hard

Given an array A of integers, return the number of non-empty continuous subarrays that satisfy the following condition:

The leftmost element of the subarray is not larger than other elements in the subarray.

Example 1:

Input: nums = [1,4,2,5,3]

Output: 11

Explanation:

• There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

Example 2:

Input: nums = [3,2,1]

Output: 3

Explanation:

• The 3 valid subarrays are: [3],[2],[1].

Example 3:

Input: nums = [2,2,2]

Output: 6

Explanation:

• There are 6 valid subarrays: [2],[2],[2],[2,2],[2,2],[2,2,2].

Constraints:

• 1 <= len(nums) <= 50000

• 0 <= nums[i] <= 100000

class Solution1(object):
    def validSubarrays(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        s = []

        for num in nums:
            while s and s[-1] > num:
                s.pop()
            s.append(num);
            result += len(s)

        return result

s = Solution1()
nums = [1,4,2,5,3]
assert s.validSubarrays(nums) == 11
nums = [3,2,1]
assert s.validSubarrays(nums) == 3
nums = [2,2,2]
assert s.validSubarrays(nums) == 6

See also:

https://leetcode.com/problems/number-of-valid-subarrays